// 二叉搜索树节点类
class TreeNode {
    val;
    left;
    right;
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// 二叉搜索树类
class BST {
    constructor() {
        this.root = null; //根节点
    }

    // 插入节点
    insert(val) {
        this.root = this._insert(this.root, val);
    }

    _insert(node, val) {
        if (node === null) { //插入的节点为空,则直接创建一个节点返回出去当作根节点
            return new TreeNode(val);
        }
        if (val < node.val) { //如果插入的数据小于当前值,则插入到左子树
            node.left = this._insert(node.left, val); //递归插入到左子树,继续保持满足二叉搜索树的特性
        } else if (val > node.val) { //如果插入的数据大于当前值,则插入到右子树
            node.right = this._insert(node.right, val); //递归插入到右子树,继续保持满足二叉搜索树的特性
        }
        // 如果相等则不插入（或根据需求调整）
        return node;  //这里很关键,还是等于传入的node
    }

    // 搜索节点
    search(val) {
        return this._search(this.root, val);
    }

    _search(node, val) { //递归搜索节点
        if (node === null) return null;
        if (node.val === val) return node;
        if (val < node.val) {
            return this._search(node.left, val);
        } else {
            return this._search(node.right, val);
        }
    }


    //删除一个节点
    delete(val) {
        this.root = this._delete(this.root, val);
    }

    _delete(node, val) {
        if (node === null) return null;
        
        if (val < node.val) {
            // 递归删除左子树
            node.left = this._delete(node.left, val);
        } else if (val > node.val) {
            // 递归删除右子树
            node.right = this._delete(node.right, val);
        } else {
            // 找到要删除的节点
            if (node.left === null) {
                // 情况1：没有左子节点，用右子节点替换
                return node.right;
            } else if (node.right === null) {
                // 情况2：没有右子节点，用左子节点替换
                return node.left;
            } else {
                // 情况3：有两个子节点
                // 找到右子树的最小节点（中序遍历的下一个节点）
                let minNode = this._findMin(node.right);
                // 用最小节点的值替换当前节点
                node.val = minNode.val;
                // 删除右子树中的最小节点
                node.right = this._delete(node.right, minNode.val);
            }
        }
        return node;
    }
    
    // 找到最小节点
    _findMin(node) {
        while (node.left !== null) {
            node = node.left;
        }
        return node;
    }

    // 前序遍历
    preOrder() {
        const res = [];
        function traverse(node) {
            if (node === null) return;
            res.push(node.val);
            traverse(node.left);
            traverse(node.right);
        }
        traverse(this.root);
        return res;
    }

    // 中序遍历
    inOrder() {
        const res = [];
        function traverse(node) {
            if (node === null) return;
            traverse(node.left);
            res.push(node.val);
            traverse(node.right);
        }
        traverse(this.root);
        return res;
    }

    // 后序遍历
    postOrder() {
        const res = [];
        function traverse(node) {
            if (node === null) return;
            traverse(node.left);
            traverse(node.right);
            res.push(node.val);
        }
        traverse(this.root);
        return res;
    }

    // 层序遍历
    levelOrder() {
        const res = [];
        if (!this.root) return res;
        const queue = [this.root];
        while (queue.length) {
            const node = queue.shift();
            res.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        return res;
    }
}


// 测试
let bst = new BST();
[5, 3, 7, 2, 4, 6, 8].forEach(val => bst.insert(val));
/**
 * 
 *       5
 *      / \
 *     3   7
 *    / \ / \
 *   2  4 6  8
 * 
 */
console.log("前序遍历:", bst.preOrder());
console.log("中序遍历:", bst.inOrder());
console.log("后序遍历:", bst.postOrder());
console.log("层序遍历:", bst.levelOrder());
console.log("搜索4:", bst.search(4));
console.log("搜索10:", bst.search(10));


console.log("删除节点7:", bst.delete(7));
console.log("前序遍历:", bst.preOrder());